#include<iostream>
#include<stdbool.h>
using namespace std;
template <class k > 
struct BinarySearchTreenode
{
	typedef BinarySearchTreenode<k> Node;
	Node* _left;
	Node* _right;
	k _key;
	//c++
	BinarySearchTreenode(const k& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
		{}
};
template<class k>
class BSTree
{
	typedef BinarySearchTreenode<k> Node;
public:
	BSTree()
	{}
	
	bool FindR(const k& key)
	{
		return _FindR(_root,key);
	}
	bool InsetR(const k& key)
	{
		return _InsetR(_root,key);
	}
	void putnode()
	{
		_putnode(_root);
	}
	bool earse(const k& key)
	{
		return _earse(_root, key);
	}
private:
	bool _earse(Node*& root, const k& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key > key)
		{
			_earse(root->_left, key);
		}
		else if (root->_key < key)
		{
			_earse(root->_right, key);
		}
		else
		{
			
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* minnode = root->_right;
				Node* minparent = root;
				while (minnode->_left)
				{
					minparent = minnode;
					minnode = minnode->_left;
				}
				root->_key = minnode->_key;
				if (minnode = minparent->_left)
				{
					minparent->_left = minnode->_right;
				}
				else
				{
					minparent->_right = minnode->_right;
				}
				
				delete minnode;
			}
		}
	}
	
	void _putnode(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}
		//
		_putnode(root->_left);
		cout << root->_key<<" ";
		_putnode(root->_right);
	}

	bool _InsetR(Node*& root, const k& key)
	{
		if (root == nullptr)
		{
			Node* tmp = new Node(key);
			root = tmp;
		}
		if (root->_key > key)
		{
			_InsetR(root->_left, key);
		}
		else if (root->_key < key)
		{
			_InsetR(root->_right, key);
		}
		else
		{
			return false;
		}
	}
	bool _FindR(const Node*& root, const k& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key < key)
		{
			_FindR(root->_right,key);
		}
		else if (root->_key > key)
		{
			_FindR(root->_left, key);
		}
		else
		{
			return true;
		}
	}
	Node* _root;
};
